package com.mlh.linkedlist;

// 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表如果是，返回 true ；否则，返回 false 。
public class 回文链表 {
    /*
    第一种想法：把节点全部压入栈然后一个一个弹出
    将弹出的元素从头结点开始比较  如果全部相同则满足回文
    时间复杂度为o(n) 空间复杂度是o(n)
     */
    /*
    第二种想法：利用快慢指针
    我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。
    虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。
    该方法虽然可以将空间复杂度降到 O(1)，但是在并发环境下，该方法也有缺点。
    在并发环境下，函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执行过程中链表会被修改。

    整个流程可以分为以下五个步骤：
    (1)找到前半部分链表的尾节点。
    (2)反转后半部分链表。
    (3)判断是否回文。
    (4)恢复链表。
    (5)返回结果。

    步骤一:我们可以计算链表节点的数量，然后遍历链表找到前半部分的尾节点。
    我们也可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。
    当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
    若链表有奇数个节点，则中间的节点应该看作是前半部分。

    步骤二:可以使用「206. 反转链表」问题中的解决方法来反转链表的后半部分。

    步骤三:比较两个部分的值，当后半部分到达末尾则比较完成，可以忽略计数情况中的中间节点。

    步骤四:与步骤二使用的函数相同，再反转一次恢复链表本身。

    总结：写代码时 可以把一些代码包装成方法使用
    代码出错出现在  当链表有奇数个节点时  fast和slow会走到同一个节点  这个我没写出来
    还有一个注意点就是  逆袭后半部分链表后 在链表中间部分会形成一个环
     */
    public boolean method1(ListNode head) {
        // 只有一个节点时 必定是回文
        if (head.next == null || head == null) {
            return true;
        }
        // 设置快慢指针
        ListNode fast = head.next;
        ListNode slow = head;
        // 找到中间节点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode temp = slow.next;// 逆转链表的头结点
        ListNode next;
        while (temp != null) {
            next = temp.next;
            temp.next = slow;
            slow = temp;
            temp = next;
        }
        // 此时slow在尾结点的位置
        fast = head;
        while (fast.val == slow.val) {
            if (fast.next == slow || fast == slow) {
                return true;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return false;
    }

    public boolean practice(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 逆转链表 --反转点设置为slow的下一个
        // 偶数时  slow每次会遍历到前一半的最后一个节点
        // 奇数时  slow会遍历到中间节点
        ListNode tail = 反转链表.practice(slow.next);
        while (tail!=null) {
            if (head.val != tail.val ) {
                return false;
            }
            head=head.next;
            tail=tail.next;
        }
        return true;
    }

    public boolean practice2(ListNode head) {
        if(head==null){
            return true;
        }
        ListNode slow=head,fast=head.next;
        // 该循环会slow会指向偶数的一半 奇数的中点
        while (fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode newHead = 反转链表.practice(slow.next);
        while(newHead!=null){
            if(newHead.val!=head.val){
                return false;
            }
            newHead=newHead.next;
            head=head.next;
        }
        return true;
    }
}